package Ex1;

import java.util.Iterator;

public class LinkedBinarySearchTree<E extends Comparable<E>> implements BinarySearchTree<E>, Iterable<E>{
	
	private BinaryTree<E> tree;
	private int internalcount; // count the nodes in the binary search tree
	
	public LinkedBinarySearchTree() {
		tree = new LinkedBinaryTree<E>();
		tree.addRoot(null);
		internalcount = 0;
	}
	
	private Position<E> treeSearch(E e, Position<E> p) {
		if (p.element() == e)
			return p;
		else if (e.compareTo(p.element()) < 0)
			return treeSearch(e, tree.left(p));
		else 
			return treeSearch(e, tree.right(p));
	}

	@Override
	public int size() {
		return internalcount;
	}

	@Override
	public boolean isEmpty() {
		return (internalcount == 0);
	}

	@Override
	public void instert(E e) {
		Position<E> p = treeSearch(e, tree.root());
		if (tree.isExternal(p)) {
			tree.replace(p, e);
			tree.insertLeft(p, null);
			tree.insertRight(p, null);
			internalcount++;
		}
		
	}

	@Override
	public void remove(E e) {
		Position<E> p = treeSearch(e, tree.root());
		if (tree.isInternal(p)) {
			if (tree.isExternal(tree.left(p)))
				removeExternal(tree.left(p));
			else if (tree.isExternal(tree.right(p)))
				removeExternal(tree.right(p));
			else {
				Position<E> rem = tree.right(p);
				while(tree.isInternal(tree.left(rem)))
					rem = tree.left(rem);
				
				tree.replace(p, rem.element());
				removeExternal(tree.left(rem));
			}
		}
	}

	private void removeExternal(Position<E> p) {
		if (!tree.isExternal(p))
			throw new RuntimeException(
					"Can only remove external nodes (and it's parent) from a non-empty tree.");
		
		Position<E> parent = tree.parent(p);
		tree.remove(p);
		tree.remove(parent);
		internalcount--;
	}
	
	@Override
	public Position<E> search(E e) {
		Position<E> p = treeSearch(e, tree.root());
		
		if (tree.isExternal(p))
			return null;
		else
			return p;
	}

	
	@Override
	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}
}
